Most image compression schemes are designed for “natural images”, e.g. photos taken by a digital camera. For natural images, strong correlation exists among neighboring pixels. Hence, most image compression schemes work by de-correlating the pixels using prediction/transform, or both. This results in a sparse histogram of the prediction residuals or transform coefficients. FIG. 1 illustrates histogram 12 of an image 10 after an 8×8 discrete cosine transform 16. As shown in FIG. 1, the histogram 12 has a single peak 14, which is located around 0. Quantization is applied (if necessary), and entropy coding of the (quantized) prediction residuals or transform coefficients is performed. The entropy coder is generally designed for distributions similar to those shown in FIG. 1. In other words, if the distribution has significantly different shape, the coding performance could be poor.
However, there is also a large amount of “unnatural” images in need of compression. These images often comprise graphics or text, which typically have a large dynamic range strong contrast, sharp edges, strong textures, and sparse histograms. FIG. 2 is an example of such an “unnatural image”.
These types of images usually cannot be well handled by conventional image compression algorithms. Inter-pixel correlation is weaker, and prediction or transform does not provide a sparse distribution as for natural images.
One attempt to address compression of these images is called “histogram packing”, where the encoder goes through the whole image, computes the histogram, and does a non-linear mapping of the pixels before compressing the image. The compression requires a two-pass processing, causing increased memory cost and more computations. The bitstream is not scalable, which means that the decoder needs the whole bitstream to decode the image. Partial reconstruction is not possible without re-encoding.